package dmsxl.huisu;

import java.util.*;

/**
 * Author: Zhang Dongwei
 * Date: 2023/7/17 19:56
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 *
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 *
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 */
public class hs19_332 {

    static private LinkedList<String> res;
    static private LinkedList<String> path = new LinkedList<>();

    public static void main(String[] args) {
        List<List<String>> tickets = new ArrayList<>();
        List<String> list = new ArrayList<>();
        list.add("MUC");
        list.add("LHR");
        tickets.add(new ArrayList<>(list));
        List<String> list1 = new ArrayList<>();
        list.add("JFK");
        list.add("MUC");
        tickets.add(new ArrayList<>(list1));
        List<String> list2 = new ArrayList<>();
        list.add("SFO");
        list.add("SJC");
        tickets.add(new ArrayList<>(list2));
        List<String> list3 = new ArrayList<>();
        list.add("LHR");
        list.add("SFO");
        tickets.add(new ArrayList<>(list3));
        List<String> list4 = new ArrayList<>();
        list4 = findItinerary(tickets);
        System.out.println(list4);
    }

    public static List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        path.add("JFK");
        boolean[] used = new boolean[tickets.size()];
        backTracking((ArrayList) tickets, used);
        return res;
    }

    public static boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
        if (path.size() == tickets.size() + 1) {
            res = new LinkedList(path);
            return true;
        }

        for (int i = 0; i < tickets.size(); i++) {
            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
                path.add(tickets.get(i).get(1));
                used[i] = true;
                if (backTracking(tickets, used)) {
                    return true;
                }
                used[i] = false;
                path.removeLast();
            }
        }
        return false;
    }
}
